/*
 * Copyright Benjamin Ylvisaker 2012.  License information to come
 * later.  For now it's not licensed for any use.
 *
 */

#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include "pointer_set.h"
#include "parse_cfg_file.h"

#define LINE_BUF_SZ 1024
#define FIRST_REAL_BBL_IDX 10

void dump_bbl( BBL_CTX bbl, FILE *f )
{
    uint32_t i;
    /* XXX: Need to figure out live-out mismatches */
    fprintf( f, "{\n  \"id\":%i,\n  \"flags\":%i,\n  \"ins_ct\":%i,  \"live_in_ct\":%lu,"
             "  \"live_out_ct\":%lu,  \"live_ins\":\n  [\n",
             bbl->id, bbl->flags, bbl->ins_ct, bbl->live_ins.sz, bbl->live_outs_all.sz );

    for( i = 0; i < bbl->live_ins.sz; ++i )
    {
        if( i > 0 )
            fprintf( f, ",\n" );
        fprintf( f, "    { \"name\":\"%s\" }", (char*)bbl->live_ins.data[i] );
    }
    fprintf( f, "\n  ],\n  \"live_outs\":\n  [\n" );
    for( i = 0; i < bbl->live_outs_all.sz; ++i )
    {
        if( i > 0 )
            fprintf( f, ",\n" );
        fprintf( f, "    { \"name\":\"%s\" }", (char*)bbl->live_outs_all.data[i] );
    }
    fprintf( f, "\n  ],\n  \"inss\":\n  [\n" );
    for( i = 0; i < bbl->ins_ct; ++i )
    {
        uint8_t j;
        INSTR ins = &bbl->inss[ i ];
        if( i > 0 )
            fprintf( f, ",\n" );
        fprintf( f, "    {\n      \"opc\":\"%s\",\n      \"flags\":%i,\n      \"disas\":\"%s\",\n"
                 "      \"r_ct\":%i,\n      \"w_ct\":%i,\n      \"reads\": [\n",
                 ins->opc, ins->flags, ins->disas, ins->r_ct, ins->w_ct );
        for( j = 0; j < ins->r_ct; ++j )
        {
            ANNOT_REG reg = &ins->reads[ j ];
            if( j > 0 )
                fprintf( f, ",\n" );
            fprintf( f, "        { \"n\":\"%s\", \"fn\":\"%s\", \"fl\": %i }",
                     reg->name, reg->full_name, reg->flags );
        }
        fprintf( f, "\n      ],\n      \"writes\": [\n" );
        for( j = 0; j < ins->w_ct; ++j )
        {
            ANNOT_REG reg = &ins->writes[ j ];
            if( j > 0 )
                fprintf( f, ",\n" );
            fprintf( f, "        { \"n\":\"%s\", \"fn\":\"%s\", \"fl\": %i }",
                     reg->name, reg->full_name, reg->flags );
        }
        fprintf( f, "\n      ]\n    }" );
    }
    fprintf( f, "\n  ]\n}\n" );
}

void call_return_foo( void )
{
    uint32_t i, ct = 0;
    for( i = 0; i <= bbl_max_idx; ++i )
    {
        BBL_CTX bbl = &bbls[ i ];
        if( bbl->id
            && bbl->exec_ct
            && ( bbl->flags & BBLF_DUMMY_CALL_RET ) )
        {
            uint32_t j;
            ++ct;
            printf( "hallooooo %p %p %p flags:%x  %i   %i  %i  preds:%i  succs:%i\n",
                    bbl->preds, bbl, bbl->succs,
                    bbl->flags, i, ct, bbl_max_idx, bbl->pred_ct, bbl->succ_ct );
            printf( "  preds: " );
            for( j = 0; j < bbl->pred_ct; ++j )
            {
                EDGE_LINK link = &bbl->preds[ j ];
                //EDGE_LABEL label = &edges[ link->label ];
                printf( "%i (%p) ", link->bbl, link );
            }
            printf( "     succs: " );
            for( j = 0; j < bbl->succ_ct; ++j )
            {
                EDGE_LINK link = &bbl->succs[ j ];
                //EDGE_LABEL label = &edges[ link->label ];
                printf( "%i (%p) ", link->bbl, link );
            }
            printf( "\n" );
            assert( !bbl->pred_ct == !bbl->succ_ct );


        }
#if 0

struct _BBL_CTX
{
    uint64_t exec_ct;
    /* preds and succs are arrays of indices into the edges arrays in the global context */
    uint32_t id, img_puid, pred_ct, pred_cap, succ_ct, succ_cap, ins_ct;
    EDGE_LINK preds, succs;
    INSTR inss;
    BBL_FLAGS flags;
    _PTR_SET local_live_ins, live_ins, writes, live_outs_any, live_outs_all;
};

#define BBLF_NONE           ((BBL_FLAGS) 0x0)
#define         ((BBL_FLAGS) 0x1)
#define BBLF_IS_ENTRY       ((BBL_FLAGS) 0x2)
#define         ((BBL_FLAGS) 0x4)
#define BBLF_IS_STAT_RET    ((BBL_FLAGS) 0x8)
#define BBLF_IS_DYN_RET     ((BBL_FLAGS)0x10)
#define BBLF_DUMMY_CALL_RET ((BBL_FLAGS)0x20)
#endif

    }
}

/* Begin worklist algorithm */

typedef struct _FIFO_QUEUE _FIFO_QUEUE, *FIFO_QUEUE;
struct _FIFO_QUEUE
{
    size_t front, back, cap, elem_sz;
    void *data;
};

void fifo_queue_open_alloced( FIFO_QUEUE q, size_t elem_sz, size_t init_cap )
{
    assert( init_cap > 0 );
    q->front = 0;
    q->back = 0;
    q->cap = init_cap + 1;
    q->elem_sz = elem_sz;
    q->data = calloc( q->cap, elem_sz );
}

void fifo_queue_close_alloced( FIFO_QUEUE q )
{
    free( q->data );
}

void fifo_queue_push( FIFO_QUEUE q, void *elem )
{
    if( ( q->back + 1 ) % q->cap == q->front )
    {
        size_t old_cap = q->cap;
        q->cap *= 2;
        q->data = realloc( q->data, q->cap * q->elem_sz );
        if( q->front > q->back )
        {
            memcpy( &((char*)q->data)[ old_cap * q->elem_sz ], q->data, q->back * q->elem_sz );
            q->back += old_cap;
        }
    }
    memcpy( q->data + q->back * q->elem_sz, elem, q->elem_sz );
    q->back = ( q->back + 1 ) % q->cap;
}

void *fifo_queue_pop( FIFO_QUEUE q )
{
    void *rv;
    if( q->front == q->back )
        return NULL;
    rv = &((char*)q->data)[ q->front * q->elem_sz ];
    assert( q->front < q->cap );
    q->front = ( q->front + 1 ) % q->cap;
    return rv;
}

bool fifo_queue_is_empty( FIFO_QUEUE q )
{
    return q->front == q->back;
}

void compute_global_live_ins( PTR_SET callee_regs )
{
    size_t ctr = 0;
    _FIFO_QUEUE worklist;
    uint32_t i;
    fifo_queue_open_alloced( &worklist, sizeof( uint32_t ), 10 );
    for( i = 0; i <= bbl_max_idx; ++i )
    {
        BBL_CTX bbl = &bbls[ i ];
        if( !bbl->id || ( bbl->flags & BBLF_DUMMY_CALL_RET ) )
            continue;
#if 0
#define BBLF_NONE           ((BBL_FLAGS) 0x0)
#define         ((BBL_FLAGS) 0x1)
#define BBLF_IS_ENTRY       ((BBL_FLAGS) 0x2)
#define         ((BBL_FLAGS) 0x4)
#define BBLF_IS_STAT_RET    ((BBL_FLAGS) 0x8)
#define BBLF_IS_DYN_RET     ((BBL_FLAGS)0x10)
#define BBLF_DUMMY_CALL_RET ((BBL_FLAGS)0x20)
#endif

        fifo_queue_push( &worklist, &bbls[i].id );
    }
    uint32_t *bbl_id_ptr;
    while( ( bbl_id_ptr = (uint32_t*)fifo_queue_pop( &worklist ) ) )
    {
        uint32_t bbl_id = *bbl_id_ptr;
        BBL_CTX bbl = &bbls[ bbl_id ];
        /* Note: exclude the call-return connections from liveness consideration */
        if( bbl->flags & BBLF_DUMMY_CALL_RET )
            continue;
        for( i = 0; i < bbl->succ_ct; ++i )
        {
            EDGE_LINK link = &bbl->succs[ i ];
            EDGE_LABEL label = &edges[ link->label ];
            /* XXX: hack to approximate sleeping value thing */
            if( !label->exec_ct
                /*|| bbl->exec_ct / label->exec_ct > 100*/ )
                continue;
            ptr_set_union( &bbl->live_ins, &label->live_in_to_succ );
        }
        /* XXX: hack to approximate proper calling convention handling */
        if( bbl->flags & ( BBLF_IS_EXIT | BBLF_IS_CALL ) )
        {
            // ptr_set_diff ( &bbl->live_ins, callee_regs );
        }
        ptr_set_diff ( &bbl->live_ins, &bbl->writes );
        ptr_set_union( &bbl->live_ins, &bbl->local_live_ins );
        for( i = 0; i < bbl->pred_ct; ++i )
        {
            EDGE_LINK link = &bbl->preds[ i ];
            EDGE_LABEL label = &edges[ link->label ];
            size_t prev_sz = label->live_in_to_succ.sz;
            ptr_set_union( &label->live_in_to_succ, &bbl->live_ins );
            if( label->live_in_to_succ.sz > prev_sz )
            {
                fifo_queue_push( &worklist, &link->bbl );
            }
        }
        if( ctr % 8000 == 17 || bbl_id == 27913 )
        {
            printf( "live-ins computing ... -- %i -- %i -- ", bbl_id, (int)ctr );
            log_bbl( bbl );
        }
        ++ctr;
    }
    fifo_queue_close_alloced( &worklist );
}

/* End worklist algorithm */

void and_now_the_live_outs( void )
{
    uint32_t i;
    for( i = 0; i <= bbl_max_idx; ++i )
    {
        uint32_t j;
        BBL_CTX bbl = &bbls[ i ];
        if( !bbl->id || ( bbl->flags & BBLF_DUMMY_CALL_RET ) )
            continue;
        ptr_set_open_alloced( &bbl->live_outs_any, 1 );
        ptr_set_open_alloced( &bbl->live_outs_all, 1 );
        if( bbl->succ_ct < 1 )
            continue;
        BBL_CTX succ = &bbls[ bbl->succs[ 0 ].bbl ];
        ptr_set_union( &bbl->live_outs_any, &succ->live_ins );
        ptr_set_union( &bbl->live_outs_all, &succ->live_ins );
        for( j = 1; j < bbl->succ_ct; ++j )
        {
            EDGE_LINK link = &bbl->succs[ j ];
            EDGE_LABEL label = &edges[ link->label ];
            /* XXX better handling of does edge ever execute */
            if( label->exec_ct )
                continue;
            succ = &bbls[ bbl->succs[ j ].bbl ];
            ptr_set_union    ( &bbl->live_outs_any, &succ->live_ins );
            ptr_set_intersect( &bbl->live_outs_all, &succ->live_ins );
        }
    }
}

/* Run scheduling on each BBL */
void schedule_bbls( uint32_t *bbl_ids, uint32_t num_bbls_to_schedule )
{
    uint32_t i;
    for( i = 0; i < num_bbls_to_schedule; ++i )
    {
        BBL_CTX bbl = &bbls[ bbl_ids[ i ] ];
        /* if( bbl->ins_ct > 9 || bbl->live_ins.sz > 8 ) */
        /* { */
        /*     printf( "Too big: is: %i  lis:%lu   ", bbl->ins_ct, bbl->live_ins.sz ); */
        /*     //continue; */
        /* } */
        printf( "\n" );
        char buf[ LINE_BUF_SZ ];
        assert( LINE_BUF_SZ >
                snprintf( buf, LINE_BUF_SZ, "bbl_%i_", bbl->id ) );
        char *out_fname = strdup( tempnam( NULL, buf ) );
        printf( "Translate!(%u/%u) is: %i  lis:%lu  out name: %s\n",
                i, num_bbls_to_schedule, bbl->ins_ct, bbl->live_ins.sz, out_fname );
        FILE *out_file = fopen( out_fname, "w" );
        assert( out_file );
        dump_bbl( bbl, out_file );
        fclose( out_file );
        assert( LINE_BUF_SZ >
                snprintf( buf, LINE_BUF_SZ, "bbl_%i", bbl->id ) );
        char *in_fname  = strdup( tempnam( NULL, "bbl_res" ) );
        assert( LINE_BUF_SZ >
                snprintf( buf, LINE_BUF_SZ, "queue_monster %s %s", out_fname, in_fname ) );
        assert( !system( buf ) );
        FILE *in_file = fopen( in_fname, "r" );
        assert( in_file );
        fclose( in_file );

        assert( !unlink( out_fname ) );
        assert( !unlink( in_fname ) );
        free( out_fname );
        free( in_fname );
    }
}

/* Comparison function for BBLs that orders by execution count times
 * instruction count. */
int bblcmp( const void *s1, const void *s2 )
{
    uint32_t id1 = *(uint32_t *)s1, id2 = *(uint32_t *)s2;
    BBL_CTX bbl1 = &bbls[ id1 ], bbl2 = &bbls[ id2 ];
    int64_t importance1 = bbl1->exec_ct, importance2 = bbl2->exec_ct;
    importance1 *= bbl1->ins_ct;
    importance2 *= bbl2->ins_ct;
    importance1 = importance2 - importance1;
    return importance1 > 0 ? 1 : ( importance1 < 0 ? -1 : 0 );
}

/**
 * usage: Passing a "BBL CFG" file
 */
int main( int argc, char **argv )
{
    _PTR_SET callee_save_regs;
    uint32_t i, j, *bbl_ids_in_priority_order;
    if( argc < 2 )
    {
        fprintf( stderr, "Need file name\n" );
        return -1;
    }
    printf( "huh? %lu\n", sizeof( char ) );
    FILE *cfg_file = fopen( argv[ 1 ], "r" );
    if( !cfg_file )
    {
        fprintf( stderr, "Failed to read CFG file %s\n", argv[ 1 ] );
    }

    registers.size = 0;
    registers.cap = 10;
    registers.pool = calloc( registers.cap, sizeof( registers.pool[0] ) );
    opcodes.size = 0;
    opcodes.cap = 10;
    opcodes.pool = calloc( opcodes.cap, sizeof( opcodes.pool[0] ) );


    parse_cfg_file( cfg_file );

    call_return_foo();

    bbl_ids_in_priority_order = malloc( bbl_ct * sizeof( bbl_ids_in_priority_order[0] ) );
    assert( bbl_ids_in_priority_order );

    uint64_t total_instr_execs = 0, total_instr_execs2 = 0;

    for( i = 0, j = 0; i <= bbl_max_idx; ++i )
    {
        if( bbls[ i ].id )
        {
            assert( j < bbl_ct );
            bbl_ids_in_priority_order[ j ] = bbls[ i ].id;
            total_instr_execs += bbls[ i ].exec_ct * bbls[ i ].ins_ct;
            ++j;
        }
    }
    assert( j == bbl_ct );
    mergesort( bbl_ids_in_priority_order, bbl_ct, sizeof( bbl_ids_in_priority_order[0] ), bblcmp );

    ptr_set_open_alloced( &callee_save_regs, 8 );
#define FIND_CALLEE_REGISTER( name ) \
    do { \
        char *canonical_name = name_universe_find( name, &registers ); \
        if( canonical_name ) \
            ptr_set_insert( &callee_save_regs, canonical_name ); \
    } while( 0 )

    FIND_CALLEE_REGISTER( "rbx" );
    FIND_CALLEE_REGISTER( "rsp" );
    FIND_CALLEE_REGISTER( "rbp" );
    FIND_CALLEE_REGISTER( "r12" );
    FIND_CALLEE_REGISTER( "r13" );
    FIND_CALLEE_REGISTER( "r14" );
    FIND_CALLEE_REGISTER( "r15" );
    FIND_CALLEE_REGISTER( "x87 CW" );

    compute_global_live_ins( &callee_save_regs );
    and_now_the_live_outs();

    log_reg_set( &callee_save_regs );
    printf( "\n" );
    for( i = 0; i < 10000 && i < bbl_ct; ++i )
    {
        BBL_CTX bbl = &bbls[ bbl_ids_in_priority_order[ i ] ];
        total_instr_execs2 += bbl->exec_ct * bbl->ins_ct;
        if( i % 100 == 17 )
        {
            log_bbl( bbl );
            printf( "  > %lli / %lli = %lli%%   %i / %i = %i\n", total_instr_execs, total_instr_execs2, 100 * total_instr_execs / total_instr_execs2, bbl_ct, i+1, bbl_ct / (i+1) );
        }
    }

    schedule_bbls( bbl_ids_in_priority_order, 10 );

    return 0;
}
